package backtrackStudy;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class BacktraceStudy08 {

    private static List<List<String>> ans =  new LinkedList<>();

    /**
     * 问题：N 皇后
     * n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
     *
     * 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
     *
     * 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
     *
     * 题解方法总结：如果下标和取值一一对应，可以用数组进行标记。如果不一一对应，可以使用Set进行记录，Set的底层是红黑树
     * @param args
     */
    public static void main(String[] args) {

    }

    public static List<List<String>> solveNQueen(int n){
        //存放路径位置
        LinkedList<Integer> trace = new LinkedList<>();
        //记录行
        boolean[] rowVisited = new boolean[n];
        Arrays.fill(rowVisited, false);
        //记录列
        boolean[] columnVisited = new boolean[n];
        //记录斜线
        //制作棋盘
        char[][] board = new char[n][n];
        //填充棋盘
        for (int i = 0; i < n; i++){
            for (int j = 0; j < n; j++){
                board[i][j] = '.';
            }
        }
        backtrace(board, 0, n);
        return ans;
    }

    public static void backtrace(char[][] board, int pos, int n){
        //定义出口
        if (pos == n){
            LinkedList<String> temp = new LinkedList<>();
            for (int i = 0; i < n; i++){
                temp.add(new String(board[i]));
            }
            ans.add(temp);
            return;
        }

        //定义循环体
        for (int i = 0; i < n; i++){
            boolean flag = false;
            //重定义选择列表
            for (int j = 0; j <= pos; j++){
                if (board[j][i] == 'Q'){
                    flag = true;
                    break;
                }

                if (pos-j>=0 && i+j<n && board[pos-j][i+j]=='Q'){
                    flag = true;
                    break;
                }
                if (pos-j>=0 && i-j>=0 && board[pos-j][i-j]=='Q'){
                    flag = true;
                    break;
                }
            }
            if (flag){
                continue;
            }
            //选择
            board[pos][i] = 'Q';
            backtrace(board, pos+1, n);
            board[pos][i] = '.';
        }
    }
}
